// step 2# 定义栈结构体
typedef struct {
    struct TreeNode** data;     // 栈中存储的是 TreeNode* 类型的指针
    int top;                    // 栈顶索引
    int capacity;               // 栈容量
} Stack;

// step 3# 创建一个栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));            // 分配栈结构内存
    stack->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * capacity); // 分配数据数组
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

// step 4# 判断栈是否为空
bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

// step 5# 压栈操作
void push(Stack* stack, struct TreeNode* node) {
    if (stack->top + 1 < stack->capacity) {
        stack->data[++(stack->top)] = node;
    }
}

// step 6# 弹栈操作
struct TreeNode* pop(Stack* stack) {
    if (!isEmpty(stack)) {
        return stack->data[(stack->top)--];
    }
    return NULL;
}

// step 7# 释放栈内存
void freeStack(Stack* stack) {
    free(stack->data);
    free(stack);
}

// step 8# 主函数：返回前序遍历结果数组
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // step 8.1# 边界情况处理
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    int* result = (int*)malloc(sizeof(int) * 100);          // 前序遍历结果数组（假设最多100个节点）
    *returnSize = 0;

    Stack* stack = createStack(100);                        // 创建栈，最多支持100个节点
    push(stack, root);                                      // step 8.2# 根节点入栈

    // step 8.3# 模拟递归过程
    while (!isEmpty(stack)) {
        struct TreeNode* node = pop(stack);                 // 弹出栈顶节点
        result[(*returnSize)++] = node->val;                // 记录节点值

        if (node->right) push(stack, node->right);          // 右子树入栈（先入后出）
        if (node->left) push(stack, node->left);            // 左子树入栈
    }

    freeStack(stack);                                       // 释放栈内存
    return result;
}
